package com.fary.chapter01_aqs.ext_aqs;

import com.fary.chapter01_aqs.ext_condition.FaryCondition;
import sun.misc.Unsafe;

import java.io.Serializable;
import java.lang.reflect.Field;
import java.util.concurrent.locks.LockSupport;

public class FaryAbstractQueuedSynchronizer extends FaryAbstractOwnableSynchronizer {

    private static final Unsafe unsafe;
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;

    static {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");//通过反射获取Unsafe的成员变量theUnsafe
            field.setAccessible(true);//设置为内存可以取
            unsafe= (Unsafe) field.get(null);//获取值
            stateOffset = unsafe.objectFieldOffset(FaryAbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset(FaryAbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset(FaryAbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset(FaryNode.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset(FaryNode.class.getDeclaredField("next"));
        } catch (Exception ex) { throw new Error(ex); }
    }
    protected final boolean compareAndSetState(int expect, int update) {
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }
    private static final boolean compareAndSetWaitStatus(FaryNode node, int expect, int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset, expect, update);
    }
    private final boolean compareAndSetTail(FaryNode expect, FaryNode update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }
    private static final boolean compareAndSetNext(FaryNode node, FaryNode expect, FaryNode update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }
    private final boolean compareAndSetHead(FaryNode update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }



    // 锁池队列头部
    private transient volatile FaryNode head;
    // 锁池队列尾部
    private transient volatile FaryNode tail;
    // 锁状态 0：无锁 1：加锁 重入锁+1
    private volatile int state;
    static final long spinForTimeoutThreshold = 1000L;

    protected FaryAbstractQueuedSynchronizer() { }

    private void setHead(FaryNode node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    protected final int getState() {
        return state;
    }
    protected final void setState(int newState) {
        state = newState;
    }

    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }
    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }
    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }
    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 获取锁
     */
    public final void acquire(int arg) {
        if (!tryAcquire(arg) && acquireQueued(addWaiter(FaryNode.EXCLUSIVE), arg))
            selfInterrupt();
    }
    /**
     * 释放锁
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            FaryNode h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

    /**
     * 将当前线程节点添加到锁池队列中
     */
    private FaryNode addWaiter(FaryNode mode) {
        // 以独占模式把当前线程封装成一个Node节点
        FaryNode node = new FaryNode(Thread.currentThread(), mode);
        // 尝试快速入队
        FaryNode pred = tail;
        // 如果尾节点不为空，尝试直接追加在尾节点
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        // 自旋追加在尾节点
        enq(node);
        return node;
    }

    /**
     * 自旋追加在尾节点
     */
    private FaryNode enq(final FaryNode node) {
        for (;;) {
            FaryNode t = tail;
            if (t == null) {
                if (compareAndSetHead(new FaryNode()))
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }


    /**
     * 这里是判断CLH队列中是否存在排队节点  存在 返回 true  不存在返回false
     * @return
     */
    public final boolean hasQueuedPredecessors() {
        FaryNode t = tail;
        FaryNode h = head;
        FaryNode s;
        // true: (1)头结点 != 尾节点 & 下一个节点=null
        //          eg:1.线程1持有锁
        //             2.线程2竞争锁失败准备存入队列,cas创建head结点,但未执行tail=head,
        //             3.线程1释放锁
        //             4.线程3进来判断,head=new Node(),tail=null,head.next=null
        //       (2)头结点 != 尾节点 & 下一个节点!=null & 下一个节点的线程!=当前线程
        //          eg:1.线程1持有锁
        //             2.线程2竞争锁失败存入队列
        //             3.线程3竞争锁进来判断,head=new Node(),tail=node2,head.next=node2,s.thread!=currentThread
        // false:(1)头结点 == 尾节点 (第一次获取锁head=tail=null)
        //          eg:1.线程1持有锁
        //             2.线程2竞争锁失败准备存入队列,cas创建head结点,刚执行完tail=head,
        //             3.线程1释放锁
        //             4.线程3直接获取锁,不用排队!!!
        //       (2)头结点 != 尾节点 & 下一个节点!=null & 下一个节点的线程=当前线程(唤醒下一个节点)
        //          eg:1.线程1持有锁
        //             2.线程2竞争锁失败存入队列
        //             3.线程1释放锁,唤醒线程2
        //             4.线程2进来判断,head=new Node(),tail=node2,head.next=node2,s.thread=currentThread
        return h != t && ((s = h.next) == null || s.thread != Thread.currentThread());
    }

    /**
     * 此主要是通过自旋方式获取同步状态
     */
    final boolean acquireQueued(final FaryNode node, int arg) {
        boolean failed = true;
        try {
            // 默认线程没有被中断过
            boolean interrupted = false;
            for (;;) {
                // 获取该节点的前驱节点p
                final FaryNode p = node.predecessor();
                // 如果p是头节点并且能获取到同步状态
                if (p == head && tryAcquire(arg)) {
                    // 把当前节点设为头节点
                    setHead(node);
                    p.next = null; // help GC
                    // 标志--表示成功获取同步状态,默认是true，表示失败
                    failed = false;
                    // 返回该线程在获取到同步状态的过程中有没有被中断过
                    return interrupted;
                }
                // 用于判断是否挂起当前线程
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            // 如果fail为true,直接移除当前节点
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 如果线程获取同步状态失败就要检查它的节点status,要保证prev = node.prev
     */
    private static boolean shouldParkAfterFailedAcquire(FaryNode pred, FaryNode node) {
        // 获取当前节点的前驱节点的waitStatus
        int ws = pred.waitStatus;
        // 如果前驱节点的ws = SIGNAL,表示前驱节点释放后会唤起当前线程,可以安全的挂起当前线程
        if (ws == FaryNode.SIGNAL)
            // 能够挂起当前线程直接返回true
            return true;
        // 前驱节点的ws > 0,说明ws = Cancelled,表示前驱线程被取消,从前驱节点继续往前遍历,直到找到第一个前驱节点的ws<= 0为止
        if (ws > 0) {
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            // 这种情况表示前驱节点的 ws = 0 或者 ws = PROPAGATE,我们需要一个SIGNAL,但是不能挂起当前线程
            compareAndSetWaitStatus(pred, ws, FaryNode.SIGNAL);
        }
        return false;
    }

    // 调用LockSupport的park方法挂起当前线程,返回该线程是否被中断过,如果被中断过,直接设置interrupted = true.
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

    /**
     * 取消当前节点
     *  1. node本身就是尾节点,直接把node的prev设为尾节点
     *  2. node的prev不是头结点,直接把prev和node的next进行连接
     *  3. node的prev是头结点,使用unparkSuccessor唤醒后继节点
     */
    private void cancelAcquire(FaryNode node) {
        // 当前节点不存在的话直接忽略
        if (node == null)
            return;
        // 把当前节点的线程设为null
        node.thread = null;
        // 获取当前节点的前驱pred
        FaryNode pred = node.prev;
        // 如果pred的ws > 0,直接跳过pred继续往前遍历,直到pred的ws <= 0
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;
        // 获取pred的后继predNext
        FaryNode predNext = pred.next;
        // 把node节点的ws设为CANCELLED
        node.waitStatus = FaryNode.CANCELLED;
        // 如果node是尾节点,利用CAS把pred设为尾节点,predNext为null
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            // pred不是头结点 && pred的线程不为空 && pred.ws = SIGNAL
            // 利用CAS把node的next设为pred的next节点
            int ws;
            if (pred != head && ((ws = pred.waitStatus) == FaryNode.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, FaryNode.SIGNAL))) && pred.thread != null) {
                FaryNode next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                // node是头结点,唤起它的后继节点
                unparkSuccessor(node);
            }
            node.next = node; // help GC
        }
    }

    /**
     * 如果node存在唤醒它的后继节点
     */
    private void unparkSuccessor(FaryNode node) {
        // 获取node的ws,如果ws<0,使用CAS把node的ws设为0,表示释放同步状态
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);
        /**
         * 通常情况下, 要唤醒的节点就是自己的后继节点
         * 如果后继节点存在且也在等待锁, 那就直接唤醒它
         * 但是有可能存在 后继节点取消等待锁 的情况
         * 此时从尾节点开始向前找起, 直到找到距离head节点最近的ws<=0的节点
         */
        FaryNode s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (FaryNode t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }

    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    /**
     *  如有必要，在取消等待后将节点转移到同步队列。如果线程在被signal()之前被取消，则返回true。
     */
    final boolean transferAfterCancelledWait(FaryNode node) {
        // 如果成功设置结点的状态位，则说明中断发生时，没有signal的调用，因为signal方法会将状态设置为0；
        if (compareAndSetWaitStatus(node, FaryNode.CONDITION, 0)) {
            // 将当前线程添加到aqs的等待的队列中
            enq(node);
            return true;
        }
        // 上面的代码唯一失败的可能是在此期间，condition被调用了signal方法，导致上面的compareAndSetWaitStatus返回false
        // 如果不在Sync队列中，则让步给其他线程执行，直到当前的node已经被signal方法添加到Sync队列中；
        while (!isOnSyncQueue(node))
            Thread.yield();
        return false;
    }

    final int fullyRelease(FaryNode node) {
        boolean failed = true;
        try {
            // 获取阻塞队列中当前线程节点的锁状态值
            // 调用getState()先获取阻塞队列中当前线程节点的锁状态值，这个值可能大于1表示多次重入，然后调用release(savedState)释放所有锁，如果释放成功返回锁状态值。
            int savedState = getState();
            // 释放当前线程节点锁
            if (release(savedState)) {
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            // 释放失败将节点等待状态设置成关闭
            if (failed)
                node.waitStatus = FaryNode.CANCELLED;
        }
    }

    /**
     * (1）第一步先判断次节点是否CONDITION状态或者前置节点是否存在，如果是表明不在队列中返回false，阻塞队列中的状态一般是0或者SIGNAL状态而且如果当前如果当前节点在队列阻塞中且未被激活前置节点一定不为空。
     *（2）第二步判断节点的下个节点是否存在，如果存在则表明当前节点已加入到阻塞队列中。
     *（3）如果以上2点都没法判断，也有可能刚刚加入到同步阻塞队列中，所以调用findNodeFromTail(Node node)做最后的遍历查找。查找从队列尾部开始查，从尾部开始查的原因是可能刚刚加入到同步阻塞队列中，从尾部能快速定位。
     */
    final boolean isOnSyncQueue(FaryNode node) {
        // 此处判断当前Node的状态，如果是CONDITION，表明是正常的没有被唤醒的节点
        // 如果node的前继结点为null，表明是刚刚持有锁的线程
        if (node.waitStatus == FaryNode.CONDITION || node.prev == null)
            return false;
        // 如果node结点既不是在等待队列中，也不是刚刚持有锁的线程，并且有后继结点，那么他肯定在Syn队列中
        if (node.next != null)
            return true;
        // 遍历查找当前节点是否在同步阻塞队列中
        return findNodeFromTail(node);
    }

    /**
     * 从尾节点开始找，直到头结点
     */
    private boolean findNodeFromTail(FaryNode node) {
        FaryNode t = tail;
        for (;;) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }

    final boolean transferForSignal(FaryNode node) {
        if (!compareAndSetWaitStatus(node, FaryNode.CONDITION, 0))
            return false;
        // 返回同步队列的尾节点
        FaryNode p = enq(node);
        int ws = p.waitStatus;
        // 1.在从condition队列到同步队列之前，tail节点被取消了
        // 2.在从condition队列到同步队列之后，tail节点没被取消，执行完ws > 0 之后，这段时间，被取消了？就通过!compareAndSetWaitStatus(p, ws, Node.SIGNAL)再判断一下
        // 这个时候偷偷的提前执行一波，就算不提前执行，AQS队列会不断的把取消节点取消掉，最终还是被unpark的
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, FaryNode.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }

    public final void acquireSharedInterruptibly(int arg) throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
    }

    private void doAcquireSharedInterruptibly(int arg) throws InterruptedException {
        final FaryNode node = addWaiter(FaryNode.SHARED);
        boolean failed = true;
        try {
            for (;;) {
                final FaryNode p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 1. propagate > 0
     * 在ReentrantReadWriteLock中走到setHeadAndPropagate，只可能是propagate > 0，所以后面判断旧、新head的逻辑就被短路了。
     * 而在Semaphore中走到setHeadAndPropagate，propagate是可以等于0的，表示没有剩余资源了，故propagate > 0不满足，往后判断。
     * 2. h == null || h.waitStatus < 0
     * 首先判断旧head是否为null，一般情况下是不可能是等于null，除非旧head刚好被gc了。h == null不满足，继续判断h.waitStatus < 0，h.waitStatus可能等于0，可能等于-3。
     * h.waitStatus=0的情况，某个线程释放了锁(release or releaseShared)或者前一个节点获取共享锁传播setHeadAndPropagate，唤醒后继节点的时候将h.waitStatus=-1设置为0。
     * h.waitStatus=-3，doReleaseShared唤醒head后继节点后h.waitStatus从-1到0，还没来得及更新head，即被唤醒的共享节点还没有setHeadAndPropagate，又有其他线程doReleaseShared唤醒head后继节点h.waitStatus从0到-3。
     */
    private void setHeadAndPropagate(FaryNode node, int propagate) {
        FaryNode h = head; // Record old head for check below
        setHead(node);
        if (propagate > 0 || h == null || h.waitStatus < 0 || (h = head) == null || h.waitStatus < 0) {
            FaryNode s = node.next;
            // 此时node节点为头结点,如果也是尾节点 s==null成立(以防空指针)
            // 所以直接判断下一节点是否为共享节点
            if (s == null || s.isShared())
                doReleaseShared();
        }
    }

    /**
     * 当我们再次回到for(;;)循环中，由于此时当前节点的前驱节点已经成为了新的head，
     * 所以它可以参与抢锁，由于它抢的是共享锁，所以大概率它是抢的到的，所以极有可能它不会被挂起。
     * 这有可能导致在上面的doReleaseShared调用unparkSuccessor方法unpark了一个并没有被park的线程。
     * 然而，这一操作是被允许的，当我们unpark一个并没有被park的线程时，该线程在下一次调用park方法时就不会被挂起，
     * 而这一行为是符合我们的场景的——因为当前的共享锁处于可获取的状态，后继的线程应该直接来获取锁，不应该被挂起。
     *
     *
     * 线程3没有获取到锁,刚存入队列,
     * 线程4没有获取到锁,还没存入队列
     * 此时线程1释放锁,判断头节点的waitState=0,不需要唤醒节点,只需要修改head节点waitState=-3,因为没有节点需要唤醒
     * 线程2也释放锁了,也不需要唤醒节点,也不用修改head节点waitState
     * 线程3获取到锁,propagate = 1,还有一个票据,需要唤醒线程4
     *
     *
     * 线程3没有获取到锁,刚存入队列,刚修改head节点的waitState=-1,还没有阻塞,准备再次尝试获取锁
     * 线程4没有获取到锁,还没存入队列
     * 此时线程1释放锁,判断头节点的waitState=-1,直接unpark线程3,并修改头节点的waitState=0
     * 线程5直接抢到票据,获取到锁
     * 线程3又没有获取到锁,修改头节点的waitState=-1,挂起当前线程,由于前面已经unpark,所以不会中断,继续尝试获取锁
     */
    private void doReleaseShared() {
        for (;;) {
            FaryNode h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == FaryNode.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, FaryNode.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h);
                } else if (ws == 0 && !compareAndSetWaitStatus(h, 0, FaryNode.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            if (h == head)                   // loop if head changed
                break;
        }
    }

    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    public class FaryConditionObject implements FaryCondition, Serializable {
        private static final long serialVersionUID = 1173984872572414699L;
        private transient FaryNode firstWaiter;
        private transient FaryNode lastWaiter;
        // 该模式意味着在退出等待时重新中断
        private static final int REINTERRUPT =  1;
        // 该模式意味着在退出等待时抛出InterruptedException
        private static final int THROW_IE    = -1;

        /**
         * （1）先判断是否当前线程是否被中断中断则抛出中断异常如果未中断调用addConditionWaiter()加入等待队列
         * （2）调用fullyRelease(node)释放锁使同步阻塞队列的下个节点线程能获取锁。
         * （3）调用isOnSyncQueue(node)判断是否在同步阻塞队列，这里的加入同步阻塞队列操作是在另一个线程调用signal()后加入，如果不在同步阻塞队列会进行阻塞直到被激活。
         * （4）如果被激活然后调用checkInterruptWhileWaiting(node)判断是否被中断并获取中断模式。
         * （5）继续调用isOnSyncQueue(node)判断是否在同步阻塞队列。
         * （6）是则调用acquireQueued(node, savedState) 获取锁，这里如果获取不到也会被阻塞，获取不到原因是在第一次调用isOnSyncQueue(node)前，可能另一个线程已经调用signal()后加入到同步阻塞队列，然后调用acquireQueued(node, savedState) 获取不到锁并阻塞。acquireQueued(node, savedState)也会返回当前线程是否被中断，如果被中断设置中断模式。
         * （7）在激活后调用unlinkCancelledWaiters()清理等待队列的已经被激活的节点。
         * （8）最后判断当前线程是否被中断，如果被中断则对中断线程做处理。
         */
        public final void await() throws InterruptedException {
            // 判断当前线程是否被中断中断则抛出中断异常
            if (Thread.interrupted())
                throw new InterruptedException();
            // 加入等待队列
            FaryNode node = addConditionWaiter();
            // 释放当前线程锁
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            // 自旋挂起，判断当前的线程是否在Syn队列中
            // 直到被唤醒或者超时或者CANCELLED等
            // 因为上一步已经释放了锁，也就是说此时可能有线程已经获取锁同时可能已经调用了signal方法，如果已经唤醒，那么就不应该park了，而是退出while方法，从而继续争抢锁
            while (!isOnSyncQueue(node)) {
                // 阻塞当前线程
                LockSupport.park(this);
                // 判断是否被中断
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            // 获得锁，并将自己从Condition队列中释放(此处修改了node结点的状态位，具体的清除由其他线程完成)，表明自己不再需要锁。
            // 这里获得锁后的状态位不是THROW_IE就是REINTERRUPT，那么在后面就一定会被抛出异常或者中断线程
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            // node结点不是最后一个结点，这个时候就要清除该node结点了，顺手把其他不是Condition状态位的结点也清了
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            // 抛出InterruptedException，重新中断当前线程，或不执行任何操作，具体取决于模式
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
        }

        private FaryNode addConditionWaiter() {
            // 获取等待队列尾部节点
            FaryNode t = lastWaiter;
            // 如果尾部状态不为CONDITION，如果已经被"激活"，清理之，然后重新获取尾部节点
            if (t != null && t.waitStatus != FaryNode.CONDITION) {
                unlinkCancelledWaiters();
                t = lastWaiter;
            }
            // 创建以当前线程为基础的节点，并将节点模式设置成CONDITION
            FaryNode node = new FaryNode(Thread.currentThread(), FaryNode.CONDITION);
            // 如果尾节点不存在，说明队列为空，将头节点设置成当前节点
            if (t == null)
                firstWaiter = node;
            // 如果尾节点存在，将此节点设置成尾节点的下个节点
            else
                t.nextWaiter = node;
            // 将尾节点设置成当前节点
            lastWaiter = node;
            return node;
        }

        /**
         * 遍历Condition的条件队列，将状态不为Condition（已被Cancel的节点）移除
         */
        private void unlinkCancelledWaiters() {
            FaryNode t = firstWaiter;
            // 遍历过程中的最后一个Condition条件队列中的有效结点
            FaryNode trail = null;
            // 从条件队列的第一个结点开始遍历
            while (t != null) {
                FaryNode next = t.nextWaiter;
                // 当前结点的等待状态位不是CONDITION,即该节点已被唤醒，移除该结点
                if (t.waitStatus != FaryNode.CONDITION) {
                    t.nextWaiter = null;
                    if (trail == null)
                        firstWaiter = next;
                    else
                        trail.nextWaiter = next;
                    // 说明该结点已经是Condition队列的最后一个结点，可以设置lastWaiter的指向了
                    if (next == null)
                        lastWaiter = trail;
                } else
                    trail = t;
                t = next;
            }
        }

        // 检查中断，如果在signalled前被中断返回THROW_IE，如果在signalled后被中断返回REINTERRUPT
        // 若没有被中断则返回0
        private int checkInterruptWhileWaiting(FaryNode node) {
            return Thread.interrupted() ? (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : 0;
        }

        private void reportInterruptAfterWait(int interruptMode) throws InterruptedException {
            if (interruptMode == THROW_IE)
                throw new InterruptedException();
            else if (interruptMode == REINTERRUPT)
                selfInterrupt();
        }

        public final void signal() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            FaryNode first = firstWaiter;
            if (first != null)
                doSignal(first);
        }

        private void doSignal(FaryNode first) {
            do {
                if ( (firstWaiter = first.nextWaiter) == null)
                    lastWaiter = null;
                first.nextWaiter = null;
            } while (!transferForSignal(first) && (first = firstWaiter) != null);
        }

        public final void signalAll() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            FaryNode first = firstWaiter;
            if (first != null)
                doSignalAll(first);
        }

        private void doSignalAll(FaryNode first) {
            lastWaiter = firstWaiter = null;
            do {
                FaryNode next = first.nextWaiter;
                first.nextWaiter = null;
                transferForSignal(first);
                first = next;
            } while (first != null);
        }

        public final long awaitNanos(long nanosTimeout) throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            FaryNode node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }
    }

    /**
     * 节点
     */
    static final class FaryNode {
        /** 前驱节点 */
        volatile FaryNode prev;
        /** 后继节点 */
        volatile FaryNode next;
        /** 线程 */
        volatile Thread thread;
        /** 独占节点 */
        static final FaryNode EXCLUSIVE = null;
        /** 共享节点 */
        static final FaryNode SHARED = new FaryNode();
        /** 线程的等待状态 表示后继线程需要被唤醒 */
        static final int SIGNAL    = -1;
        /** 线程的等待状态 表示线程已经被取消 */
        static final int CANCELLED =  1;
        /** 线程的等待状态 表示线程在Condition上 */
        static final int CONDITION = -2;
        /** 表示下一个acquireShared需要无条件的传播 */
        static final int PROPAGATE = -3;
        /**
         *   SIGNAL:     当前节点的后继节点处于等待状态时,如果当前节点的同步状态被释放或者取消,必须唤起它的后继节点
         *   CANCELLED:  一个节点由于超时或者`中断需要在CLH队列中取消等待状态,被取消的节点不会再次等待
         *   CONDITION:  当前节点在等待队列中,只有当节点的状态设为0的时候该节点才会被转移到同步队列
         *   PROPAGATE:  下一次的共享模式同步状态的获取将会无条件的传播
         *   waitStatus的初始值时0,使用CAS来修改节点的状态
         */
        volatile int waitStatus;
        /** 独占模式 共享模式 */
        FaryNode nextWaiter;

        FaryNode() { }
        FaryNode(Thread thread, FaryNode mode) {
            this.nextWaiter = mode;
            this.thread = thread;
        }
        FaryNode(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }

        /**
         * 返回上一个节点
         */
        final FaryNode predecessor() throws NullPointerException {
            FaryNode p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        final boolean isShared() {
            return nextWaiter == SHARED;
        }

    }
}
